package 面试v1.字节;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class Sort {


    // 冒泡排序，a表示数组，n表示数组大小
    public void bubbleSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 0; i < n; ++i) {
            // 提前退出冒泡循环的标志位
            boolean flag = false;
            for (int j = 0; j < n - i - 1; ++j) {
                if (a[j] > a[j + 1]) { // 交换
                    int tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                    flag = true;  // 表示有数据交换
                }
            }
            if (!flag) break;  // 没有数据交换，提前退出
        }
    }


    // 插入排序，a表示数组，n表示数组大小
    public void insertionSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j + 1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j + 1] = value; // 插入数据
        }
    }

    public static void mergeSort(int[] array, int left, int right, int[] tempArray) {
        if (left < right) {
            int mid = (left + right) / 2;//中间索引
            //向左递归分解
            mergeSort(array, left, mid, tempArray);
            //向右递归分解
            mergeSort(array, mid + 1, right, tempArray);
            //合并
            sort(array, left, mid, right, tempArray);
        }
    }

    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(16, 0.75f, true) {
        // 当调用map的put()和putAll()方法后会调用removeEldestEntry()检查是否应该删除eldest元素
        // 这里表示存放时如果超过最大容量应该移除末尾元素
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > 20;
        }
    };

    /**
     * @param array     待排序的数组
     * @param left      左边有序子数组的初始索引
     * @param mid       中间索引
     * @param right     右边的索引
     * @param tempArray 用于排序时存储未完全排序的数组
     */
    private static void sort(int[] array, int left, int mid, int right, int[] tempArray) {
        int i = left;//初始化i，左边有序子数组的初始索引
        int j = mid + 1;//初始化j，右边有序子数组的初始索引
        int index = 0;//用于标识tempArray数组当前所在的下标
        //(一)
        //先把左右两边(有序)的子数组按照规则填充到tempArray数组
        //直到左右两边的有序子数组，有一边处理完毕为止
        while (i <= mid && j <= right) {//当左右子数组都没完成数据转移时
            if (array[i] <= array[j]) {//左边的元素小于右边的元素，将该元素加入到临时数组中,
                // 一直循环直到找到一个元素比右边的大，将转移权交给右边的子数组
                tempArray[index] = array[i];
                i++;//向右移动一位
                index++;
            } else {//右边的元素小于左边的元素，将该元素加入到临时数组中,
                // 一直循环直到找到一个元素比左边的大，将转移权交给左边的子数组
                tempArray[index] = array[j];
                j++;//向右移动一位
                index++;
            }
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid) {//说明左边的子数组有剩余元素
            tempArray[index] = array[i];
            i++;
            index++;
        }
        while (j <= right) {//说明右边的子数组有剩余元素
            tempArray[index] = array[j];
            j++;
            index++;
        }

        //(三)
        //将tempArray数组的元素拷贝到array
        // 注意，并不是每次都是拷贝所有元素到array（待排序）数组中
        // 第一次合并tempLeft = 0 , right = 1
        // 第二次合并tempLeft= 2 right = 3
        // 第三次合并 tempLeft=0 right = 3
        // 最后一次tempLeft= 0 right = 7
        index = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            array[tempLeft] = tempArray[index];
            index++;
            tempLeft++;
        }
    }

}

//本地进程：
//管道 |
//消息队列
//信号
//信号量
//远程：
//socket

//事务一致性
//2pc
//3pc
//tcc
//本地消息表
//消息事务
